Internet Surfer 2.0

home *** CD-ROM | disk | FTP | other *** search

/ Internet Surfer 2.0 / Internet Surfer 2.0 (Wayzata Technology) (1996).iso / pc / textfile / faqs / puzz_faq / part11 < prev next >

Wrap

Internet Message Format | 1992-12-26 | 59.0 KB

Xref: bloom-picayune.mit.edu rec.puzzles:18146 news.answers:3077 Newsgroups: rec.puzzles,news.answers Path: bloom-picayune.mit.edu!enterpoop.mit.edu!snorkelwacker.mit.edu!usc!wupost!spool.mu.edu!uunet!questrel!chris From: uunet!questrel!chris (Chris Cole) Subject: rec.puzzles FAQ, part 11 of 15 Message-ID: <puzzles-faq-11_717034101@questrel.com> Followup-To: rec.puzzles Summary: This posting contains a list of Frequently Asked Questions (and their answers). It should be read by anyone who wishes to post to the rec.puzzles newsgroup. Sender: chris@questrel.com (Chris Cole) Reply-To: uunet!questrel!faql-comment Organization: Questrel, Inc. References: <puzzles-faq-1_717034101@questrel.com> Date: Mon, 21 Sep 1992 00:09:38 GMT Approved: news-answers-request@MIT.Edu Expires: Sat, 3 Apr 1993 00:08:21 GMT Lines: 1889 Archive-name: puzzles-faq/part11 Last-modified: 1992/09/20 Version: 3 ==> induction/hanoi.p <== Is there an algorithom for solving the hanoi tower puzzle for any number of towers? Is there an equation for determining the minimum number of moves required to solve it, given a variable number of disks and towers? ==> induction/hanoi.s <== The best way of thinking of the Towers of Hanoi problem is inductively. To move n disks from post 1 to post 2, first move (n-1) disks from post 1 to post 3, then move disk n from post 1 to post 2, then move (n-1) disks from post 3 to post 2 (same procedure as moving (n-1) disks from post 1 to post 3). In order to figure out how to move (n-1) disks from post 1 to post 3, first move (n-2) disks . . . . As far as an algorithm which straightens out any legal position is concerned, the algorithm would go something like this: 1. Find the smallest disk. Call the post that it's on post 1. 2. Find the smallest disk which is not on post 1. This disk is, say, size k. (I am calling the smallest disk size 1 here.) Call the post that disk k is on post 2. Disks 1 through (k-1) are then all stacked up correctly on post 1 disk k is on top of post 2. This follow from the fact that the disks are in a legal postition. 3. Move disks 1 through (k-1) from post 1 to post 2, ignoring the other disks. This is just the standard Tower of Hanoi problem for (k-1) disks. 4. If the disks are not yet correctly arranged, repeat from step 1. In fact, this gives the straightening with the fewest number of moves. With 3 towers, for N number of disks, the formula for the minimum number of moves to complete the puzzle correctly is: (2^N) - 1 This bit of ancient folklore was invented by De Parville in 1884. ``In the great temple at Benares, says he, beneath the dome which marks the centre of the world, rests a brass plate in which are fixed three diamond needles, each a cubit high and as thick as the body of a bee. On one of these needles, at the creation, God placed sixty-four discs of pure gold, the largest disc resting on the brass plate, and the others getting smaller and smaller up to the top one. This is the Tower of Bramah. Day and night unceasingly the priests transfer the discs from one diamond needle to another according to the fixed and immutable laws of Bramah, which require that the priest on duty must not move more than one disc at a time and that he must place this disc on a needle so that there is no smaller disc below it. When the sixty-four discs shall have been thus transferred from the needle on which at the creation God placed them to one of the other needles, tower, temple, and Brahmins alike will crumble into dust, and with a thunderclap the world will vanish.'' (W W R Ball, MATHEMATICAL RECREATIONS AND ESSAYS, p. 304) This has been discussed by several authors, e.g. Er, Info Sci 42 (1987) 137-141. Graham, Knuth and Patashnik, _Concrete_Mathematics_. There are many papers claiming to solve this, and they are probably all correct but they rely on the unproven "Frame's conjecture". In particular, for the 4 peg case the conjecture states that an optimal solution begins by forming a substack of the k smallest discs, then moving the rest, and then moving those k again; k to be determined. Here is a extensible bc program that does the same work. The output format is not that great. We get 300 numbers as output. The first hundred represent N, the next 100 represent f(N) and the last hundred represent i, which is the number of discs to move to tmp1 using f(N). For convenience, I have here some values for N <= 48. Enjoy. Sharma N 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 f(N) 1 3 5 9 13 17 25 33 41 49 65 81 97 113 129 161 193 225 257 i 0 1 1 2 2 3 3 4 5 6 6 7 8 9 10 10 11 12 13 N 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 f(N) 289 321 385 449 513 577 641 705 769 897 1025 1153 1281 1409 1537 1665 i 14 15 15 16 17 18 19 20 21 21 22 23 24 25 26 27 N 36 37 38 39 40 41 42 43 44 45 46 47 48 f(N) 1793 2049 2305 2561 2817 3073 3329 3585 3841 4097 4609 5121 5633 i 28 28 29 30 31 32 33 34 35 36 36 37 38 /* This is the bc program that gives f(N) for 4 peg case */ w = 101; /* This represents the number of disks */ m[0] = 0; m[1] = 1; m[2] = 3; m[3] = 5; m[4] = 9; m[5] = 13; m[6] = 17; /* f(n) is the function that gives the min # of moves for 4 peg case */ define f(n) { return (m[n]); } /* g(n) is the function that fives the min # of moves for 3 peg case */ define g(n) { return (2^n - 1); } /* x(n) is the Optimization Routine */ define x(n) { auto j auto r auto i if(n == 1) return (1); j = f(1) + g(n-1); for(i = 2; i < n; i++) { r = f(i) + g(n-i); if(r < j) { j = r; d = i; } } return (j); } /* main program */ for(q = 4; q < w; q++) { t = x(q-1); m[q] = 2 * t + 1; d[q] = d; }; /*This for loop prints the number of discs from 1 <= n <= w*/ for(q = 1; q < w; q++) { q; } /*This for loop prints f(n) for 1 <= n <= w */ for(q = 1; q < w; q++) { m[q]; } /*This for loop prints i for 1 <= n <= w i represents the number of disks to be moved to tmp location using f(n) N-i-1 will be moved using g(n) */ for(q = 1; q < w; q++) { d[q]; } -- sharma@sharma.warren.mentorg.com ==> induction/n-sphere.p <== With what odds do three random points on an n-sphere form an acute triangle? ==> induction/n-sphere.s <== Select three points a, b, and c, randomly with respect to the surface of an n-sphere. These three points determine a fourth, x, which is the intersection of the sphere with the axis perpendicular to the abc plane. (Choose the pole nearest the plane.) I could have, just as easily, selected x, a distance d from x, and three points d units away from x. The distribution of d is not uniform, but that's ok. For every x and d, the three points abc form an acute triangle with probability p[n-1]. By induction, p[n] = 1/4. ==> induction/paradox.p <== What simple property holds for the first 10,000 integers, then fails? ==> induction/paradox.s <== Consider the sequences defined by: s(1) = a; s(2) = b; s(n) = least integer such that s(n)/s(n-1) > s(n-1)/s(n-2). In other words, s(n) = 1+floor(s(n-1)^2/s(n-2)) for n >= 3. These sequences are similar in some ways to the classically-studied Pisot sequences. For example, if a = 1, b = 2, then we get the odd-indexed Fibonacci numbers. D. Boyd of UBC, an expert in Pisot sequences, pointed out the following. If we let a = 8, b = 55 in the definition above, then the resulting sequence s(n) appears to satisfy the following linear recurrence of order 4: s(n) = 6s(n-1) + 7s(n-2) - 5s(n-3) - 6s(n-4) Indeed, it does satisfy this linear recurrence for the first 11,056 terms. However, it fails at the 11,057th term! And s(11057) is a 9270 digit number. (The reason for this coincidence depends on a remarkable fact about the absolute values of the roots of the polynomial x^4 - 6x^3 - 7x^2 + 5x + 6.) ==> induction/party.p <== You're at a party. Any two (different) people at the party have exactly one friend in common (the friend is also at the party). Prove that there is at least one person at the party who is a friend of everyone else. Assume that the friendship relation is symmetric and not reflexive. ==> induction/party.s <== Here is an easy solution by induction. Let P be the set of people in the party, and n the size of P. If n=2 or 3, the result is trivial. Suppose now that n>3 and that the result is true for n-1. For any two distinct x,y in P, write x & y to mean that `x is a friend of y', and x ~& y to mean that `x is not a friend of y'. Take q in P. The hypothesis on the relation & is still satisfied on P-{q}; by induction, the result is thus true for P-{q}, and there is some p in P-{q} such that p & x for any x in P-{p,q}. We have two cases: a) p & q. Then the result holds for P with p. b) p ~& q. By hypothesis, there is a unique r in P-{p,q} such that p & r & q. For any x in P-{p,q}, if x & q, then p & x & q, and so x=r. Thus r is the unique friend of q. Now for any s in P-{q,r} there exists some x such that s & x & q, and so x=r. This means that r & s for any s in P-{q,r}, and as r & q, the results holds in P with r. The problem can also be solved by applying the spectral theory of graphs (see for instance Bollobas' excellent book, _Extremal Graph Theory_). The problem's condition is vacuous if there is only N=1 person at the "party", impossible if N=2 (If you aren't your own friend, nor I mine, somebody *else* must be our mutual friend), and trivial if N=3 (everybody must be everyone else's friend). Henceforth assume N>3. Let A,B be two friends, and C their mutual friend. Let a be the number of A's friends other than B and C, and likewise b,c. Each of A's friends is also friendly with exactly one other of A's friends, and with none of B and C's other friends (if A1,B1 are friends of A,B resp. and of each other then A1 and B have more than one mutual friend); likewise for B and C. Let M=N-(a+b+c+3) be the number of people not friendly with any of A,B,C. Each of them is friendly with exactly one of A's and one of B's friends; and each pair of a friend of A and a friend of B must have exactly one of them as a mutual friend. Thus M=ab; likewise M=ab=ac=bc. Thus either M and two of a,b,c vanish, or a=b=c=k (say), M=k^2, and N=k^3+3k+3. In the first case, say b=c=0; necessarily a is even, and A is a friend of everybody else at the party, each of whom is friendly with exactly one other person; clearly any such configuration (a graph of k/2+1 triangles with a common vertex) satisfies the problem's conditions). It remains to show that the second case is impossible. Since N=k^2+3k+3 does not depend on A,B,C, neither does k, and it quickly follows that the party's friendship graph is regular with reduced matrix [ 0 k+2 0 ] [ 1 1 k ] [ 0 1 k+1 ] and eigenvalues k+2 and +-sqrt(k+1) and multiplicities 1,m1,m2 for some *integers* m1 and m2 such that (m1-m2)*sqrt(k+1)=-(k+2) (because the graph's matrix has trace zero). Thus sqrt(k+1) divides k+2 and k+1 divides (k+2)^2=(k+1)(k+3)+1 which is only possible if k=0, Q.E.D. ==> induction/roll.p <== An ordinary die is thrown until the running total of the throws first exceeds 12. What is the most likely final total that will be obtained? ==> induction/roll.s <== Claim: If you throw a die until the running total exceeds n>=5, a final outcome of n+1 is more likely than any other. Assume we throw an m for a total n+k>n+1, and assume m-k>=0. Now, it is just as likely to throw an m as an m-k+1, which means that the sum n+1 is just as likely as any other. Now consider the series of throws consisting of n-5 1's followed by a 6 and note that we cannot achieve more than an n+1 by changing the last die roll. Hence, a total of n+1 is more likely than any other. ==> induction/takeover.p <== After graduating from college, you have taken an important managing position in the prestigious financial firm of "Mary and Lee". You are responsable for all the decisions concerning take-over bids. Your immediate concern is whether to take over "Financial Data". There is no doubt that you will be successful if you are the first to bid and that this will be profitable for the firm and you in the long run. However, you know that there exist another n financial firms, similar to "Mary and Lee", that are also considering the possibility. Although you are likely to be the first one to move, you know that just after a take-over there is a lot of adjustment that needs to be done. In fact, for a period of time following any take-over the successful firm becomes a prime candidate for a take-over which will cost the job of whoever is responsable for take-overs. Among all financial firms it is common knowledge that the managers responsable for take-overs are rational and intelligent. What is your best response? ==> induction/takeover.s <== Assume the takeover is wise for n. The takeover is then unwise for n+1, as the other companies now find themselves in the same situation as you for n. If the decision is unwise for n, by similar reasoning it is wise to takeover FD for n+1. Now note that for n=1 the takeover decision is clearly unwise, hence by induction you should takeover FD iff n is even. ==> logic/29.p <== Three people check into a hotel. They pay $30 to the manager and go to their room. The manager finds out that the room rate is $25 and gives $5 to the bellboy to return. On the way to the room the bellboy reasons that $5 would be difficult to share among three people so he pockets $2 and gives $1 to each person. Now each person paid $10 and got back $1. So they paid $9 each, totalling $27. The bellboy has $2, totalling $29. Where is the remaining dollar? ==> logic/29.s <== Each person paid $9, totalling $27. The manager has $25 and the bellboy $2. The bellboy's $2 should be added to the manager's $25 or subtracted from the tenants' $27, not added to the tenants' $27. ==> logic/ages.p <== 1) Ten years from now Tim will be twice as old as Jane was when Mary was nine times as old as Tim. 2) Eight years ago, Mary was half as old as Jane will be when Jane is one year older than Tim will be at the time when Mary will be five times as old as Tim will be two years from now. 3) When Tim was one year old, Mary was three years older than Tim will be when Jane is three times as old as Mary was six years before the time when Jane was half as old as Tim will be when Mary will be ten years older than Mary was when Jane was one-third as old as Tim will be when Mary will be three times as old as she was when Jane was born. HOW OLD ARE THEY NOW? ==> logic/ages.s <== The solution: Tim is 3, Jane is 8, and Mary is 15. A little grumbling is in order here, as clue number 1 leads to the situation a year and a half ago, when Tim was 1 1/2, Jane was 6 1/2, and Mary was 13 1/2. This sort of problem is easy if you write down a set of equations. Let t be the year that Tim was born, j be the year that Jane was born, m be the year that Mary was born, and y be the current year. As indefinite years come up, let y1, y2, ... be the indefinite years. Then the equations are y + 10 - t = 2 (y1 - j) y1 - m = 9 (y1 - t) y - 8 - m = 1/2 (y2 - j) y2 - j = 1 + y3 - t y3 - m = 5 (y + 2 - t) t + 1 - m = 3 + y4 - t y4 - j = 3 (y5 - 6 - m) y5 - j = 1/2 (y6 - t) y6 - m = 10 + y7 - m y7 - j = 1/3 (y8 - t) y8 - m = 3 (j - m) t = y - 3 j = y - 8 m = y - 15 ==> logic/bookworm.p <== A bookworm eats from the first page of an encyclopedia to the last page. The bookworm eats in a straight line. The encyclopedia consists of ten 1000-page volumes. Not counting covers, title pages, etc., how many pages does the bookworm eat through? ==> logic/bookworm.s <== On a book shelf the first page of the first volume is on the "inside" __ __ B| | | |F A|1 |...........................|10|R C| | | |O K| | | |N | | | |T ---------------------------------- so the bookworm eats only through the cover of the first volume, then 8 times 1000 pages of Volumes 2 - 9, then through the cover to the 1st page of Vol 10. He eats 8,000 pages. ==> logic/boxes.p <== Which Box Contains the Gold? Two boxes are labeled "A" and "B". A sign on box A says "The sign on box B is true and the gold is in box A". A sign on box B says "The sign on box A is false and the gold is in box A". Assuming there is gold in one of the boxes, which box contains the gold? ==> logic/boxes.s <== The problem cannot be solved with the information given. The sign on box A says "The sign on box B is true and the gold is in box A". The sign on box B says "The sign on box A is false and the gold is in box A". The following argument can be made: If the statement on box A is true, then the statement on box B is true, since that is what the statement on box A says. But the statement on box B states that the statement on box A is false, which contradicts the original assumption. Therefore, the statement on box A must be false. This implies that either the statement on box B is false or that the gold is in box B. If the statement on box B is false, then either the statement on box A is true (which it cannot be) or the gold is in box B. Either way, the gold is in box B. However, there is a hidden assumption in this argument: namely, that each statement must be either true or false. This assumption leads to paradoxes, for example, consider the statement: "This statement is false." If it is true, it is false; if it is false, it is true. The only way out of the paradox is to deny that the statement is either true or false and label it meaningless instead. Both of the statements on the boxes are therefore meaningless and nothing can be concluded from them. In general, statements about the truth of other statements lead to contradictions. Tarski invented metalanguages to avoid this problem. To avoid paradox, a statement about the truth of a statement in a language must be made in the metalanguage of the language. Common sense dictates that this problem cannot be solved with the information given. After all, how can we deduce which box contains the gold simply by reading statements written on the outside of the box? Suppose we deduce that the gold is in box B by whatever line of reasoning we choose. What is to stop us from simply putting the gold in box A, regardless of what we deduced? (cf. Smullyan, "What Is the Name of This Book?", Prentice-Hall, 1978, #70) ==> logic/calibans.will.p <== ---------------------------------------------- | Caliban's Will by M.H. Newman | ---------------------------------------------- When Caliban's will was opened it was found to contain the following clause: "I leave ten of my books to each of Low, Y.Y., and 'Critic,' who are to choose in a certain order. No person who has seen me in a green tie is to choose before Low. If Y.Y. was not in Oxford in 1920 the first chooser never lent me an umbrella. If Y.Y. or 'Critic' has second choice, 'Critic' comes before the one who first fell in love." Unfortunately Low, Y.Y., and 'Critic' could not remember any of the relevant facts; but the family solicitor pointed out that, assuming the problem to be properly constructed (i.e. assuming it to contain no statement superfluous to its solution) the relevant data and order could be inferred. What was the prescribed order of choosing; and who lent Caliban an umbrella? ==> logic/calibans.will.s <== Let T be "person who saw Caliban in a green tie." Let U be "person who lent Caliban an umbrella." Then the data are: (1) No T chooses before Low. (2) Either Y.Y. was in Oxford in March 1920 or the first chooser is not a U. (3) Either Low is second or Critic is not last. Consider first (3) If it could be shown that Low is first, then from (3), Critic is not last and therefore is second; i.e. the order is Low, Critic, Y.Y. Next (1) If both Critic and Y.Y. were T's would require Low first and (3) then gives the order Low-Critic-Y.Y., ie. (2) would be superfluous. Hence Critic and Y.Y. are not both T's. If neither Critic nor Y.Y. were a T, (1) would be trivially true for any ordering and therefore would give no information, i.e. would be superfluous. Hence just one of Y.Y. and Critic is a T. It follows that the only possible order in which Low is not first is: Not T, Low, T Now (2) First if Y.Y was in Oxford in March 1920, nothing follows from (2) about the order and (2) is superfluous. Hence Y.Y. was not in Oxford. If Low were a U he would not, by (2) come first, and so by (1) the order would be: Not T, Low, T i.e. (1) and (2) alone would fix an order, and (3) would be superfluous. Hence Low is not a U. It now follows, by the arguments just given for T's under (1) that just one of Y.Y. and Critic is a U. If the same one is the T and the U (2) follows from (1) (since Low is not a U); i.e (2) is superfluous. The situation is therefore: T's: just one of Y.Y. and Critic; not Low U's: the other one of Y.Y; not Low It now follows that "not T, Low, T" is impossible, for the "not T" is the "U" and therefore, by (2), is not first. Hence Low is first, and (3) gives the order: Low, Critic, Y.Y. Finally, Y.Y. is a T, and Critic is a U. For if Critic is a T, then by (1) Low precedes Critic and hence (3) allows only "Low, Critic, Y.Y"; (2) is superfluous. I.e. Critic (only) lent Caliban an umbrella. The problem is from _Problems Omnibus_ by Hubert Phillips, Arco Publications, London, 1960. Hubert Phillips was a noted puzzelist who contributed under his own name and the pseudonyms of "Caliban", "T.O. Hare", and "The Doc". ==> logic/camel.p <== An Arab sheikh tells his two sons that are to race their camels to a distant city to see who will inherit his fortune. The one whose camel is slower will win. The brothers, after wandering aimlessly for days, ask a wiseman for advise. After hearing the advice they jump on the camels and race as fast as they can to the city. What did the wiseman say? ==> logic/camel.s <== The wiseman tells them to switch camels. ==> logic/centrifuge.p <== You are a biochemist, working with a 12-slot centrifuge. This is a gadget that has 12 equally spaced slots around a central axis, in which you can place chemical samples you want centrifuged. When the machine is turned on, the samples whirl around the central axis and do their thing. To ensure that the samples are evenly mixed, they must be distributed in the 12 slots such that the centrifuge is balanced evenly. For example, if you wanted to mix 4 samples, you could place them in slots 12, 3, 6 and 9 (assuming the slots are numbered from 1 to 12 like a clock). Problem: Can you use the centrifuge to mix 5 samples? ==> logic/centrifuge.s <== The superposition of any two solutions is yet another solution, so given that the factors > 1 of 12 (2, 3, 4, 6, 12) are all solutions, the only thing to check about, for example, the proposed solution 2+3 is that not all ways of combining 2 & 3 would have centrifuge tubes from one subsolution occupying the slot for one of the tubes in another solution. For the case 2+3, there is no problem: Place 3 tubes, one in every 4th position, then place the 4th and 5th diametrically opposed (each will end up in a slot adjacent to one of the first 3 tubes). The obvious generalization is, what are the numbers of tubes that cannot be balanced? Observing that there are solutions for 2,3,4,5,6 tubes and that if X has a solution, 12-X has also one (obtained by swapping tubes and holes), it is obvious that 1 and 11 are the only cases without solutions. Here is how this problem is often solved in practice: A dummy tube is added to produce a total number of tubes that is easy to balance. For example, if you had to centrifuge just one sample, you'd add a second tube opposite it for balance. ==> logic/children.p <== A man walks into a bar, orders a drink, and starts chatting with the bartender. After a while, he learns that the bartender has three children. "How old are your children?" he asks. "Well," replies the bartender, "the product of their ages is 72." The man thinks for a moment and then says, "that's not enough information." "All right," continues the bartender, "if you go outside and look at the building number posted over the door to the bar, you'll see the sum of the ages." The man steps outside, and after a few moments he reenters and declares, "Still not enough!" The bartender smiles and says, "My youngest just loves strawberry ice cream." How old are the children? A variant of the problem is for the sum of the ages to be 13 and the product of the ages to be the number posted over the door. In this case, it is the oldest that loves ice cream. Then how old are they? ==> logic/children.s <== First, determine all the ways that three ages can multiply together to get 72: 72 1 1 (quite a feat for the bartender) 36 2 1 24 3 1 18 4 1 18 2 2 12 6 1 12 3 2 9 4 2 9 8 1 8 3 3 6 6 2 6 4 3 As the man says, that's not enough information; there are many possibilities. So the bartender tells him where to find the sum of the ages--the man now knows the sum even though we don't. Yet he still insists that there isn't enough info. This must mean that there are two permutations with the same sum; otherwise the man could have easily deduced the ages. The only pair of permutations with the same sum are 8 3 3 and 6 6 2, which both add up to 14 (the bar's address). Now the bartender mentions his "youngest"--telling us that there is one child who is younger than the other two. This is impossible with 8 3 3--there are two 3 year olds. Therefore the ages of the children are 6, 6, and 2. Pedants have objected that the problem is insoluble because there could be a youngest between two three year olds (even twins are not born exactly at the same time). However, the word "age" is frequently used to denote the number of years since birth. For example, I am the same age as my wife, even though technically she is a few months older than I am. And using the word "youngest" to mean "of lesser age" is also in keeping with common parlance. So I think the solution is fine as stated. In the sum-13 variant, the possibilities are: 11 1 1 10 2 1 9 3 1 9 2 2 8 4 1 8 3 2 7 5 1 7 4 2 7 3 3 6 6 1 6 5 2 6 4 3 The two that remain are 9 2 2 and 6 6 1 (both products equal 36). The final bit of info (oldest child) indicates that there is only one child with the highest age. This cancels out the 6 6 1 combination, leaving the childern with ages of 9, 2, and 2. ==> logic/condoms.p <== How can you have mutually safe sex with three women with only two condoms? ==> logic/condoms.s <== Use both condoms on the first woman. Take off the outer condom (turning it inside-out in the process) and set it aside. Use the inner condom alone on the second woman. Put the outer condom back on. Use it on the third woman. ==> logic/dell.p <== How can I solve logic puzzles (e.g., as published by Dell) automatically? ==> logic/dell.s <== #include <setjmp.h> #define EITHER if (S[1] = S[0], ! setjmp((S++)->jb)) { #define OR } else EITHER #define REJECT longjmp((--S)->jb, 1) #define END_EITHER } else REJECT; /* values in tmat: */ #define T_UNK 0 #define T_YES 1 #define T_NO 2 #define Val(t1,t2) (S->tmat[t1][t2]) #define CLASS(x) \ (((x) / NUM_ITEM) * NUM_ITEM) #define EVERY_TOKEN(x) \ (x = 0; x < TOT_TOKEN; x++) #define EVERY_ITEM(x, class) \ (x = CLASS(class); x < CLASS(class) + NUM_ITEM; x++) #define BEGIN \ struct state { \ char tmat[TOT_TOKEN][TOT_TOKEN]; \ jmp_buf jb; \ } States[100], *S = States; \ \ main() \ { \ int token; \ \ for EVERY_TOKEN(token) \ yes(token, token); \ EITHER /* Here is the problem-specific data */ #define NUM_ITEM 5 #define NUM_CLASS 6 #define TOT_TOKEN (NUM_ITEM * NUM_CLASS) #define HOUSE_0 0 #define HOUSE_1 1 #define HOUSE_2 2 #define HOUSE_3 3 #define HOUSE_4 4 #define ENGLISH 5 #define SPANISH 6 #define NORWEG 7 #define UKRAIN 8 #define JAPAN 9 #define GREEN 10 #define RED 11 #define IVORY 12 #define YELLOW 13 #define BLUE 14 #define COFFEE 15 #define TEA 16 #define MILK 17 #define OJUICE 18 #define WATER 19 #define DOG 20 #define SNAIL 21 #define FOX 22 #define HORSE 23 #define ZEBRA 24 #define OGOLD 25 #define PLAYER 26 #define CHESTER 27 #define LSTRIKE 28 #define PARLIA 29 char *names[] = { "HOUSE_0", "HOUSE_1", "HOUSE_2", "HOUSE_3", "HOUSE_4", "ENGLISH", "SPANISH", "NORWEG", "UKRAIN", "JAPAN", "GREEN", "RED", "IVORY", "YELLOW", "BLUE", "COFFEE", "TEA", "MILK", "OJUICE", "WATER", "DOG", "SNAIL", "FOX", "HORSE", "ZEBRA", "OGOLD", "PLAYER", "CHESTER", "LSTRIKE", "PARLIA", }; BEGIN yes(ENGLISH, RED); /* Clue 1 */ yes(SPANISH, DOG); /* Clue 2 */ yes(COFFEE, GREEN); /* Clue 3 */ yes(UKRAIN, TEA); /* Clue 4 */ EITHER /* Clue 5 */ yes(IVORY, HOUSE_0); yes(GREEN, HOUSE_1); OR yes(IVORY, HOUSE_1); yes(GREEN, HOUSE_2); OR yes(IVORY, HOUSE_2); yes(GREEN, HOUSE_3); OR yes(IVORY, HOUSE_3); yes(GREEN, HOUSE_4); END_EITHER yes(OGOLD, SNAIL); /* Clue 6 */ yes(PLAYER, YELLOW); /* Clue 7 */ yes(MILK, HOUSE_2); /* Clue 8 */ yes(NORWEG, HOUSE_0); /* Clue 9 */ EITHER /* Clue 10 */ yes(CHESTER, HOUSE_0); yes(FOX, HOUSE_1); OR yes(CHESTER, HOUSE_4); yes(FOX, HOUSE_3); OR yes(CHESTER, HOUSE_1); EITHER yes(FOX, HOUSE_0); OR yes(FOX, HOUSE_2); END_EITHER OR yes(CHESTER, HOUSE_2); EITHER yes(FOX, HOUSE_1); OR yes(FOX, HOUSE_3); END_EITHER OR yes(CHESTER, HOUSE_3); EITHER yes(FOX, HOUSE_2); OR yes(FOX, HOUSE_4); END_EITHER END_EITHER EITHER /* Clue 11 */ yes(PLAYER, HOUSE_0); yes(HORSE, HOUSE_1); OR yes(PLAYER, HOUSE_4); yes(HORSE, HOUSE_3); OR yes(PLAYER, HOUSE_1); EITHER yes(HORSE, HOUSE_0); OR yes(HORSE, HOUSE_2); END_EITHER OR yes(PLAYER, HOUSE_2); EITHER yes(HORSE, HOUSE_1); OR yes(HORSE, HOUSE_3); END_EITHER OR yes(PLAYER, HOUSE_3); EITHER yes(HORSE, HOUSE_2); OR yes(HORSE, HOUSE_4); END_EITHER END_EITHER yes(LSTRIKE, OJUICE); /* Clue 12 */ yes(JAPAN, PARLIA); /* Clue 13 */ EITHER /* Clue 14 */ yes(NORWEG, HOUSE_0); yes(BLUE, HOUSE_1); OR yes(NORWEG, HOUSE_4); yes(BLUE, HOUSE_3); OR yes(NORWEG, HOUSE_1); EITHER yes(BLUE, HOUSE_0); OR yes(BLUE, HOUSE_2); END_EITHER OR yes(NORWEG, HOUSE_2); EITHER yes(BLUE, HOUSE_1); OR yes(BLUE, HOUSE_3); END_EITHER OR yes(NORWEG, HOUSE_3); EITHER yes(BLUE, HOUSE_2); OR yes(BLUE, HOUSE_4); END_EITHER END_EITHER /* End of problem-specific data */ solveit(); OR printf("All solutions found\n"); exit(0); END_EITHER } no(a1, a2) { int non1, non2, token; if (Val(a1, a2) == T_YES) REJECT; else if (Val(a1, a2) == T_UNK) { Val(a1, a2) = T_NO; no(a2, a1); non1 = non2 = -1; for EVERY_ITEM(token, a1) if (Val(token, a2) != T_NO) if (non1 == -1) non1 = token; else break; if (non1 == -1) REJECT; else if (token == CLASS(a1) + NUM_ITEM) yes(non1, a2); for EVERY_TOKEN(token) if (Val(token, a1) == T_YES) no(a2, token); } } yes(a1, a2) { int token; if (Val(a1, a2) == T_NO) REJECT; else if (Val(a1, a2) == T_UNK) { Val(a1, a2) = T_YES; yes(a2, a1); for EVERY_ITEM(token, a1) if (token != a1) no(token, a2); for EVERY_TOKEN(token) if (Val(token, a1) == T_YES) yes(a2, token); else if (Val(token, a1) == T_NO) no(a2, token); } } solveit() { int token, tok2; for EVERY_TOKEN(token) for (tok2 = token; tok2 < TOT_TOKEN; tok2++) if (Val(token, tok2) == T_UNK) { EITHER yes(token, tok2); OR no(token, tok2); END_EITHER; return solveit(); } printf("Solution:\n"); for EVERY_ITEM(token, 0) { for (tok2 = NUM_ITEM; tok2 < TOT_TOKEN; tok2++) if (Val(token, tok2) == T_YES) printf("\t%s %s\n",names[token],names[tok2]); printf("\n"); } REJECT; } --- james@crc.ricoh.com (James Allen) ==> logic/elimination.p <== 97 baseball teams participate in an annual state tournament. The way the champion is chosen for this tournament is by the same old elimination schedule. That is, the 97 teams are to be divided into pairs, and the two teams of each pair play against each other. After a team is eliminated from each pair, the winners would be again divided into pairs, etc. How many games must be played to determine a champion? ==> logic/elimination.s <== In order to determine a winner all but one team must lose. Therefore there must be at least 96 games. ==> logic/family.p <== Suppose that it is equally likely for a pregnancy to deliver a baby boy as it is to deliver a baby girl. Suppose that for a large society of people, every family continues to have children until they have a boy, then they stop having children. After 1,000 generations of families, what is the ratio of males to females? ==> logic/family.s <== The ratio will be 50-50 in both cases. We are not killing off any fetuses or babies, and half of all conceptions will be male, half female. When a family decides to stop does not affect this fact. ==> logic/flip.p <== How can a toss be called over the phone (without requiring trust)? ==> logic/flip.s <== A flips a coin. If the result is heads, A multiplies 2 90-digit prime numbers; if the result is tails, A multiplies 3 60-digit prime numbers. A tells B the result of the multiplication. B now calls either heads or tails and tells A. A then supplies B with the original numbers to verify the flip. ==> logic/friends.p <== Any group of 6 or more contains either 3 mutual friends or 3 mutual strangers. Prove it. ==> logic/friends.s <== Take a person X. Of the five other people, there must either be at least three acquaintances of X or at least three strangers of X. Assume wlog that X has three strangers A,B,C. Unless A,B,C is the required triad of acquaintances, they must include a pair of strangers, wlog A,B. Then X,A,B is the required triad of strangers, QED. ==> logic/hundred.p <== A sheet of paper has statements numbered from 1 to 100. Statement n says "exactly n of the statements on this sheet are false." Which statements are true and which are false? What if we replace "exactly" by "at least"? ==> logic/hundred.s <== It is tempting to argue as follows: Since only one statement can be true (they are mutually contradictory), therefore 99 are false. So, all are false except for statement 99. If replaced by "at least", and the "real" number of false statements is x, then statements x+1 to 100 will be false (since they falsely claim that there are more false statements than there actually are). So, 100-x are false, ie. x=100-x, so x=50. The first 50 statements are true, and statements 51 to 100 are false. However, there is a hidden and incorrect assumption in this argument. To see this, suppose that there is one statement on the sheet and it says "One statement is false" or "At least one statement is false," either way it implies "this statement is false," which is a familiar paradoxical statement. We have learned that this paradox arises because of the false assumption that all statements are either true or false. This is the hidden assumption in the above reasoning. If it is acknowledged that some of the statements on the page may be neither true nor false (i.e., meaningless), then nothing whatsoever can be concluded about which statements are true or false. This problem has been carefully contrived to appear to be solvable (like the vacuous statement "this statement is true"). By changing the numbers in some statements and changing "true" to "false," various circular forms of the liar's paradox can be constructed. From _Litton's Problematical Recreations_ ==> logic/inverter.p <== Can a digital logic circuit with two inverters invert N independent inputs? The circuit may contain any number of AND or OR gates. ==> logic/inverter.s <== It can be shown that N inverters can invert 2N-1 independent inputs, given an unlimited supply of AND and OR gates. The classic version of this puzzle is to invert 3 independent inputs using AND gates, OR gates, and only 2 inverters. So, start with N inverters. Replace 3 of them with 2. Keep doing that until you're down to 2 inverters. I was skeptical at first, because such a design requires so much feedback that I was sure the system would oscillate when switching between two particular states. But after writing a program to test every possible state change (32^2), it appears that this system settles after a maximum of 3 feedback logic iterations. I did not include gate delays in the simulation, however, which could increase the number of iterations before the system settles. In any case, it appears that the world needs only 2 inverters! :-) ==> logic/josephine.p <== The recent expedition to the lost city of Atlantis discovered scrolls attributted to the great poet, scholar, philosopher Josephine. They number eight in all, and here is the first. THE KINGDOM OF MAMAJORCA, WAS RULED BY QUEEN HENRIETTA I. IN MAMAJORCA WOMEN HAVE TO PASS AN EXTENSIVE LOGIC EXAM BEFORE THEY ARE ALLOWED TO GET MARRIED. QUEENS DO NOT HAVE TO TAKE THIS EXAM. ALL THE WOMEN IN MAMAJORCA ARE LOYAL TO THEIR QUEEN AND DO WHATEVER SHE TELLS THEM TO. THE QUEENS OF MAMAJORCA ARE TRUTHFUL. ALL SHOTS FIRED IN MAMAJORCA CAN BE HEARD IN EVERY HOUSE. ALL ABOVE FACTS ARE KNOWN TO BE COMMON KNOWLEDGE. HENRIETTA WAS WORRIED ABOUT THE INFIDELITY OF THE MARRIED MEN IN MAMAJORCA. SHE SUMMONED ALL THE WIVES TO THE TOWN SQUARE, AND MADE THE FOLLOWING ANNOUNCEMENT. "THERE IS AT LEAST ONE UNFAITHFUL HUSBAND IN MAMAJORCA. ALL WIVES KNOW WHICH HUSBANDS ARE UNFAITHFUL, BUT HAVE NO KNOWLEDGE ABOUT THE FIDELITY OF THEIR OWN HUSBAND. YOU ARE FORBIDDEN TO DISCUSS YOUR HUSBAND'S FAITHFULNESS WITH ANY OTHER WOMAN. IF YOU DISCOVER THAT YOUR HUSBAND IS UNFAITHFUL, YOU MUST SHOOT HIM AT PRECISELY MIDNIGHT OF THE DAY YOU FIND THAT OUT." THIRTY-NINE SILENT NIGHTS FOLLOWED THE QUEEN'S ANNOUNCEMENT. ON THE FORTIETH NIGHT, SHOTS WERE HEARD. QUEEN HENRIETTA I IS REVERED IN MAMAJORCAN HISTORY. As with all philosophers Josephine doesn't provide the question, but leaves it implicit in his document. So figure out the questions - there are two - and answer them. Here is Josephine's second scroll. QUEEN HENRIETTA I WAS SUCCEEDED BY DAUGHTER QUEEN HENRIETTA II. AFTER A WHILE HENRIETTA LIKE HER FAMOUS MOTHER BECAME WORRIED ABOUT THE INFIDELITY PROBLEM. SHE DECIDED TO ACT, AND SENT A LETTER TO HER SUBJECTS (WIVES) THAT CONTAINED THE EXACT WORDS OF HENRIETTA I'S FAMOUS SPEECH. SHE ADDED THAT THE LETTERS WERE GUARENTEED TO REACH ALL WIVES EVENTUALLY. QUEEN HENRIETTA II IS REMEMBERED AS A FOOLISH AND UNJUST QUEEN. What is the question and answer implied by this scroll? ==> logic/josephine.s <== The two questions for scroll #1 were: 1. How many husbands were shot on that fateful night? 2. Why is Queen Henrietta I revered in Mamajorca? The answers are: If there are n unfaithful husbands (UHs), every wife of an UH knows of n-1 UH's while every wife of a faithful husband knows of n UHs. [this because everyone has perfect information about everything except the fidelity of their own husband]. Now we do a simple induction: Assume that there is only one UH. Then all the wives but one know that there is just one UH, but the wife of the UH thinks that everyone is faithful. Upon hearing that "there is at least one UH", the wife realizes that the only husband it can be is her own, and so shoots him. Now, imagine that there are just two UH's. Each wife of an UH assumes that the situation is "only one UH in town" and so waits to hear the other wife (she knows who it is, of course) shoot her husband on the first night. When no one is shot, that can only be because her OWN husband was a second UH. The wife of the second UH makes the same deduction when no shot is fired the first night (she was waiting, and expecting the other to shoot, too). So they both figure it out after the first night, and shoot their husbands the second night. It is easy to tidy up the induction to show that the n UHs will all be shot just on the n'th midnight. The question for scroll #2 is: 3. Why is Queen Henrietta II not? The answer is: The problem now is that QHII didn't realize that it is *critical* that all of the wives, of faithful and UH's alike, to *BEGIN*AT*THE*SAME*MOMENT*. The uncertainty of having a particular wife's notice come a day or two late makes the whole logic path fall apart. That's why she's foolish. She is unjust, because some wives, honed and crack logicians all, remember, will *incorrectly* shoot faithful husbands. Let us imagine the situation with just a SINGLE UH in the whole country. And, wouldn't you know it, the notice to the wife of the UH just happens to be held up a day, whereas everyone else's arrived the first day. Now, all of the wives that got the notice the first day know that there is just one UH in the country. And they know that the wife of that UH will think that everyone is faithful, and so they'll expect her to figure it out and shoot her husband the first night. BUT SHE DIDN"T GET THE NOTICE THE FIRST NIGHT.... BUT THE OTHER WIVES HAVE NO WAY OF KNOWING THAT. So, the wife of the UH doesn't know that anything is going on and so (of course) doesn't do anything the first night. The next day she gets the notice, figures it all out, and her husband will be history come that midnight. BUT... *every* other wife thought that there should have been a shooting the first night, and since there wasn't there must have been an additional UH, and it can only have been _her_ husband. So on the second night **ALL** of the husbands are shot. Things are much more complicated if the mix of who gets the notice when is less simple than the one I mentioned above, but it is always wrong and/or tragic. NOTE: if the wives *know* that the country courier service (or however these things get delivered) is flaky, then they can avoid the massacre, but unless the wives exchange notes no one will ever be shot (since there is always a chance that rather than _your_ husband being an UH, you could reason that it might be that the wife of one of the UH's that you know about just hasn't gotten her copy of the scroll yet). I guess you could call this case "unjust", too, since the UH's evade punishment, despite the perfect logic of the wives. ==> logic/locks.and.boxes.p <== You want to send a valuable object to a friend. You have a box which is more than large enough to contain the object. You have several locks with keys. The box has a locking ring which is more than large enough to have a lock attached. But your friend does not have the key to any lock that you have. How do you do it? ==> logic/locks.and.boxes.s <== Attach a lock to the ring. Send it to her. She attaches her own lock and sends it back. You remove your lock and send it back to her. She removes her lock. ==> logic/mixing.p <== Start with a half cup of tea and a half cup of coffee. Take one tablespoon of the tea and mix it in with the coffee. Take one tablespoon of this mixture and mix it back in with the tea. Which of the two cups contains more of its original contents? ==> logic/mixing.s <== Mixing Liquids The two cups end up with the same volume of liquid they started with. The same amount of tea was moved to the coffee cup as coffee to the teacup. Therefore each cup contains the same amount of its original contents. ==> logic/number.p <== Mr. S. and Mr. P. are both perfect logicians, being able to correctly deduce any truth from any set of axioms. Two integers (not necessarily unique) are somehow chosen such that each is within some specified range. Mr. S. is given the sum of these two integers; Mr. P. is given the product of these two integers. After receiving these numbers, the two logicians do not have any communication at all except the following dialogue: <<1>> Mr. P.: I do not know the two numbers. <<2>> Mr. S.: I knew that you didn't know the two numbers. <<3>> Mr. P.: Now I know the two numbers. <<4>> Mr. S.: Now I know the two numbers. Given that the above statements are absolutely truthful, what are the two numbers? ==> logic/number.s <== The answer depends upon the ranges from which the numbers are chosen. The unique solution for the ranges [2,62] through [2,500+] is: SUM PRODUCT X Y 17 52 4 13 The unique solution for the ranges [3,94] through [3,500+] is: SUM PRODUCT X Y 29 208 13 16 There are no unique solutions for the ranges starting with 1, and there are no solutions for ranges starting with numbers above 3. A program to compute the possible pairs is included below. #include <stdio.h> /* BEGINNING OF PROBLEM STATEMENT: Mr. S. and Mr. P. are both perfect logicians, being able to correctly deduce any truth from any set of axioms. Two integers (not necessarily unique) are somehow chosen such that each is within some specified range. Mr. S. is given the sum of these two integers; Mr. P. is given the product of these two integers. After receiving these numbers, the two logicians do not have any communication at all except the following dialogue: <<1>> Mr. P.: I do not know the two numbers. <<2>> Mr. S.: I knew that you didn't know the two numbers. <<3>> Mr. P.: Now I know the two numbers. <<4>> Mr. S.: Now I know the two numbers. Given that the above statements are absolutely truthful, what are the two numbers? END OF PROBLEM STATEMENT */ #define SMALLEST_MIN 1 #define LARGEST_MIN 10 #define SMALLEST_MAX 50 #define LARGEST_MAX 500 long P[(LARGEST_MAX + 1) * (LARGEST_MAX + 1)]; /* products */ long S[(LARGEST_MAX + 1) + (LARGEST_MAX + 1)]; /* sums */ find(long min, long max) { long i, j; /* * count factorizations in P[] * all P[n] > 1 satisfy <<1>>. */ for(i = 0; i <= max * max; ++i) P[i] = 0; for(i = min; i <= max; ++i) for(j = i; j <= max; ++j) ++P[i * j]; /* * decompose possible SUMs and check factorizations * all S[n] == min - 1 satisfy <<2>>. */ for(i = min + min; i <= max + max; ++i) { for(j = i / 2; j >= min; --j) if(P[j * (i - j)] < 2) break; S[i] = j; } /* * decompose SUMs which satisfy <<2>> and see which products * they produce. All (P[n] / 1000 == 1) satisfy <<3>>. */ for(i = min + min; i <= max + max; ++i) if(S[i] == min - 1) for(j = i / 2; j >= min; --j) if(P[j * (i - j)] > 1) P[j * (i - j)] += 1000; /* * decompose SUMs which satisfy <<2>> again and see which products * satisfy <<3>>. Any (S[n] == 999 + min) satisfies <<4>> */ for(i = min + min; i <= max + max; ++i) if(S[i] == min - 1) for(j = i / 2; j >= min; --j) if(P[j * (i - j)] / 1000 == 1) S[i] += 1000; /* * find the answer(s) and print them */ printf("[%d,%d]\n",min,max); for(i = min + min; i <= max + max; ++i) if(S[i] == 999 + min) for(j = i / 2; j >= min; --j) if(P[j * (i - j)] / 1000 == 1) printf("{ %d %d }: S = %d, P = %d\n", i - j, j, i, (i - j) * j); } main() { long min, max; for (min = SMALLEST_MIN; min <= LARGEST_MIN; min ++) for (max = SMALLEST_MAX; max <= LARGEST_MAX; max++) find(min,max); } ------------------------------------------------------------------------- = Jeff Kenton (617) 894-4508 = = jkenton@world.std.com = ------------------------------------------------------------------------- ==> logic/riddle.p <== Who makes it, has no need of it. Who buys it, has no use for it. Who uses it can neither see nor feel it. Tell me what a dozen rubber trees with thirty boughs on each might be? As I went over London Bridge I met my sister Jenny I broke her neck and drank her blood And left her standing empty It is said among my people that some things are improved by death. Tell me, what stinks while living, but in death, smells good? All right. Riddle me this: what goes through the door without pinching itself? What sits on the stove without burning itself? What sits on the table and is not ashamed? What work is it that the faster you work, the longer it is before you're done, and the slower you work, the sooner you're finished? Whilst I was engaged in sitting I spied the dead carrying the living. I know a word of letters three. Add two, and fewer there will be. I give you a group of three. One is sitting down, and will never get up. The second eats as much as is given to him, yet is always hungry. The third goes away and never returns. Whoever makes it, tells it not. Whoever takes it, knows it not. And whoever knows it wants it not. Two words, my answer is only two words. To keep me, you must give me. Sir, I bear a rhyme excelling In mystic force and magic spelling Celestial sprites elucidate All my own striving can't relate There is not wind enough to twirl That one red leaf, nearest of its clan, Which dances as often as dance it can. Half-way up the hill, I see thee at last Lying beneath me with thy sounds and sights -- A city in the twilight, dim and vast, With smoking roofs, soft bells, and gleaming lights. I am, in truth, a yellow fork From tables in the sky By inadvertent fingers dropped The awful cutlery. Of mansions never quite disclosed And never quite concealed The apparatus of the dark To ignorance revealed. Many-maned scud-thumper, Maker of worn wood, Shrub-ruster, Sky-mocker, Rave! Make me thy lyre, even as the forests are. What if my leaves fell like its own -- The tumult of thy mighty harmonies Will take from both a deep autumnal tone. This darksome burn, horseback brown, His rollock highroad roaring down, In coop and in comb the fleece of his foam Flutes and low to the body falls home. I've measured it from side to side, 'Tis three feet long and two feet wide. It is of compass small, and bare To thirsty suns and parching air. My love, when I gaze on thy beautiful face, Careering along, yet always in place -- The thought has often come into my mind If I ever shall see thy glorious behind. Then all thy feculent majesty recalls The nauseous mustiness of forsaken bowers, The leprous nudity of deserted halls -- The positive nastiness of sullied flowers. And I mark the colours, yellow and black, That fresco thy lithe, dictatorial thighs. When young, I am sweet in the sun. When middle-aged, I make you gay. When old, I am valued more than ever. I am always hungry, I must always be fed, The finger I lick Will soon turn red. All about, but cannot be seen, Can be captured, cannot be held, No throat, but can be heard. I am only useful When I am full, Yet I am always Full of holes. If you break me I do not stop working, If you touch me I may be snared, If you lose me Nothing will matter. If a man carried my burden He would break his back. I am not rich, But leave silver in my track. Until I am measured I am not known, Yet how you miss me When I have flown. I drive men mad For love of me, Easily beaten, Never free. When set loose I fly away, Never so cursed As when I go astray. I go around in circles But always straight ahead, Never complain No matter where I am led. Lighter than what I am made of, More of me is hidden Than is seen. I turn around once, What is out will not get in. I turn around again, What is in will not get out. Each morning I appear To lie at your feet, All day I will follow No matter how fast you run, Yet I nearly perish In the midday sun. Weight in my belly, Trees on my back, Nails in my ribs, Feet I do lack. Bright as diamonds, Loud as thunder, Never still, A thing of wonder. My life can be measured in hours, I serve by being devoured. Thin, I am quick Fat, I am slow Wind is my foe. To unravel me You need a simple key, No key that was made By locksmith's hand, But a key that only I Will understand. I am seen in the water If seen in the sky, I am in the rainbow, A jay's feather, And lapis lazuli. Glittering points That downward thrust, Sparkling spears That never rust. You heard me before, Yet you hear me again, Then I die, 'Till you call me again. Three lives have I. Gentle enough to soothe the skin, Light enough to caress the sky, Hard enough to crack rocks. You can see nothing else When you look in my face, I will look you in the eye And I will never lie. Lovely and round, I shine with pale light, grown in the darkness, A lady's delight. At the sound of me, men may dream Or stamp their feet At the sound of me, women may laugh Or sometimes weep When I am filled I can point the way, When I am empty Nothing moves me, I have two skins One without and one within. My tines be long, My tines be short My tines end ere My first report. What am I? ==> logic/riddle.s <== Who makes it, has no need of it. Who buys it, has no use for it. Who uses it can neither see nor feel it. coffin Tell me what a dozen rubber trees with thirty boughs on each might be? months of the year As I went over London Bridge I met my sister Jenny I broke her neck and drank her blood And left her standing empty gin It is said among my people that some things are improved by death. Tell me, what stinks while living, but in death, smells good? pig All right. Riddle me this: what goes through the door without pinching itself? What sits on the stove without burning itself? What sits on the table and is not ashamed? the sun What work is it that the faster you work, the longer it is before you're done, and the slower you work, the sooner you're finished? roasting meat on a spit Whilst I was engaged in sitting I spied the dead carrying the living. a ship I know a word of letters three. Add two, and fewer there will be. 'few' I give you a group of three. One is sitting down, and will never get up. The second eats as much as is given to him, yet is always hungry. The third goes away and never returns. stove, fire, and smoke Whoever makes it, tells it not. Whoever takes it, knows it not. And whoever knows it wants it not. counterfeit money Two words, my answer is only two words. To keep me, you must give me. your word Sir, I bear a rhyme excelling In mystic force and magic spelling Celestial sprites elucidate All my own striving can't relate ??? There is not wind enough to twirl That one red leaf, nearest of its clan, Which dances as often as dance it can. the sun, Samuel Taylor Coleridge Half-way up the hill, I see thee at last Lying beneath me with thy sounds and sights -- A city in the twilight, dim and vast, With smoking roofs, soft bells, and gleaming lights. the past, Longfellow I am, in truth, a yellow fork From tables in the sky By inadvertent fingers dropped The awful cutlery. Of mansions never quite disclosed And never quite concealed The apparatus of the dark To ignorance revealed. lightning, Emily Dickinson Many-maned scud-thumper, Maker of worn wood, Shrub-ruster, Sky-mocker, Rave! Portly pusher, Wind-slave. the ocean, John Updike Make me thy lyre, even as the forests are. What if my leaves fell like its own -- The tumult of thy mighty harmonies Will take from both a deep autumnal tone. the west wind, Percy Bysshe Shelley This darksome burn, horseback brown, His rollock highroad roaring down, In coop and in comb the fleece of his foam Flutes and low to the body falls home. river, Gerard Manley Hopkins I've measured it from side to side, 'Tis three feet long and two feet wide. It is of compass small, and bare To thirsty suns and parching air. the grave of a child, Wordsworth My love, when I gaze on thy beautiful face, Careering along, yet always in place -- The thought has often come into my mind If I ever shall see thy glorious behind. the moon, Sir Edmund Gosse Then all thy feculent majesty recalls The nauseous mustiness of forsaken bowers, The leprous nudity of deserted halls -- The positive nastiness of sullied flowers. And I mark the colours, yellow and black, That fresco thy lithe, dictatorial thighs. spider, Francis Saltus Saltus When young, I am sweet in the sun. When middle-aged, I make you gay. When old, I am valued more than ever. wine I am always hungry, I must always be fed, The finger I lick Will soon turn red. fire All about, but cannot be seen, Can be captured, cannot be held, No throat, but can be heard. wind I am only useful When I am full, Yet I am always Full of holes. sieve (or sponge) If you break me I do not stop working, If you touch me I may be snared, If you lose me Nothing will matter. heart If a man carried my burden He would break his back. I am not rich, But leave silver in my track. snail Until I am measured I am not known, Yet how you miss me When I have flown. time I drive men mad For love of me, Easily beaten, Never free. gold When set loose I fly away, Never so cursed As when I go astray. ? I go around in circles But always straight ahead, Never complain No matter where I am led. wagon wheel Lighter than what I am made of, More of me is hidden Than is seen. iceberg I turn around once, What is out will not get in. I turn around again, What is in will not get out. stopcock Each morning I appear To lie at your feet, All day I will follow No matter how fast you run, Yet I nearly perish In the midday sun. shadow Weight in my belly, Trees on my back, Nails in my ribs, Feet I do lack. ship Bright as diamonds, Loud as thunder, Never still, A thing of wonder. waterfall? (fireworks?) My life can be measured in hours, I serve by being devoured. Thin, I am quick Fat, I am slow Wind is my foe. candle To unravel me You need a simple key, No key that was made By locksmith's hand, But a key that only I Will understand. cipher I am seen in the water If seen in the sky, I am in the rainbow, A jay's feather, And lapis lazuli. blue Glittering points That downward thrust, Sparkling spears That never rust. icicle You heard me before, Yet you hear me again, Then I die, 'Till you call me again. echo Three lives have I. Gentle enough to soothe the skin, Light enough to caress the sky, Hard enough to crack rocks. water You can see nothing else When you look in my face, I will look you in the eye And I will never lie. your reflection Lovely and round, I shine with pale light, grown in the darkness, A lady's delight. pearl At the sound of me, men may dream Or stamp their feet At the sound of me, women may laugh Or sometimes weep music When I am filled I can point the way, When I am empty Nothing moves me, I have two skins One without and one within. sails? My tines be long, My tines be short My tines end ere My first report. What am I? lightning ==> logic/river.crossing.p <== Three humans, one big monkey and two small monkeys are to cross a river: a) Only humans and the big monkey can row the boat. b) At all times, the number of human on either side of the river must be GREATER OR EQUAL to the number of monkeys on THAT side. ( Or else the humans will be eaten by the monkeys!) ==> logic/river.crossing.s <== The three columns represent the left bank, the boat, and the right bank respectively. The < or > indicates the direction of motion of the boat. HHHMmm . . HHHm Mm> . HHHm <M m HHH Mm> m HHH <M mm HM HH> mm HM <Hm Hm Hm HM> Hm Hm <Hm HM mm HH> HM mm <M HHH m Mm> HHH m <M HHHm . Mm> HHHm . . HHHMmm ==> logic/ropes.p <== Two fifty foot ropes are suspended from a forty foot ceiling, about twenty feet apart. Armed with only a knife, how much of the rope can you steal? ==> logic/ropes.s <== Almost all of it. Tie the ropes together. Climb up one of them. Tie a loop in it as close as possible to the ceiling. Cut it below the loop. Run the rope through the loop and tie it to your waist. Climb the other rope (this may involve some swinging action). Pull the rope going through the loop tight and cut the other rope as close as possible to the ceiling. You will swing down on the rope through the loop. Lower yourself to the ground by letting out rope. Pull the rope through the loop. You will have nearly all the rope.